package week4;

import jsjf.exceptions.NonComparableElementException;

import java.util.Arrays;

public class ArrayOrderedList<T> extends ArrayList<T> implements OrderedListADT<T> {

    public ArrayOrderedList() {
        super();
    }

    public ArrayOrderedList(int initialCapacity) {
        super(initialCapacity);
    }

    @Override
    public void add(T element) {
        if (!(element instanceof Comparable))
            throw new NonComparableElementException("OrderedList");

        Comparable<T> comparableElement = (Comparable<T>)element;

        if (size() == list.length) {
            expandCapacity();
        }
        int scan = 0;

        // 查找插入位置
        while (scan < rear && comparableElement.compareTo(list[scan]) > 0) {
            scan++;
        }
        // 将现有元素向上移动1个
        for (int shift=rear; shift > scan; shift--) {
            list[shift] = list[shift - 1];
        }
        // 插入元素
        list[scan] = element;
        rear++;
        modCount++;
    }

    private void expandCapacity()
    {
        list = Arrays.copyOf(list, list.length * 2);
    }
}
